home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Cream of the Crop 1
/
Cream of the Crop 1.iso
/
PROGRAM
/
CUJ9208.ARJ
/
RAMEY.EXE
/
STACK.C
< prev
next >
Wrap
C/C++ Source or Header
|
1991-10-14
|
6KB
|
238 lines
/*
Copyright (c) Robert Ramey 1991. All Rights Reserved
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <links.h>
#include "psort.h"
#include "stack.h"
static STACK *u_stack; /* unused blocks */
static size_t seg_size; /* size of a memory block */
/*********************************************************************
stk_windup - eliminate vestiages of stack system from memory. Should
be called only after stk_free is called for each allocated stack.
Automatically called at exit.
**********************************************************************/
private
void
stk_windup()
{
while(u_stack->current.count--){
felem(delink((ADDRESS)u_stack, 0), 1);
}
felem((ADDRESS)u_stack, 1);
}
/*********************************************************************
stk_init - make a new stack system
**********************************************************************/
unsigned int
stk_init(size, count)
size_t size;
unsigned int count;
{
unsigned int i;
ADDRESS blk_ptr;
seg_size = size;
u_stack = stk_alloc();
if(u_stack == (STACK *)NULL)
return FALSE;
for(i = 0;i < count; ++i){
blk_ptr = mkelem(seg_size, 1);
if(blk_ptr == (ADDRESS)NULL)
break;
enlink((ADDRESS)u_stack, blk_ptr, 0);
}
onexit(stk_windup);
return u_stack->current.count = i;
}
/*********************************************************************
stk_free - free up space used by a stack
**********************************************************************/
void
stk_free(stk)
STACK *stk;
{
/* move blocks onto unused list */
while(stk->current.count--){
++u_stack->current.count;
enlink((ADDRESS)u_stack, delink((ADDRESS)stk, 0), 0);
}
/* free root of block list */
felem((ADDRESS)stk, 1);
return;
}
/*********************************************************************
stk_alloc - make a new stack
**********************************************************************/
STACK *
stk_alloc()
{
STACK *stk;
/* initialize root node to zero */
stk = (ADDRESS)mkelem(sizeof(STACK), 1);
if(stk == (STACK *)NULL){
return (STACK *)NULL;
}
/* initialize stack control structure */
link((ADDRESS)stk, NULL, 0);
stk->frame_count = 0;
stk->current.count = 0;
stk->current.size = 0;
stk->previous = stk->current;
stk->pushed = stk->current;
return stk;
}
/*********************************************************************
stk_avl - return size remaining in current segment
**********************************************************************/
/*
size_t
stk_avl(stk)
STACK *stk;
{
return stk->current.count ? stk->current.size : 0 ;
}
*/
/*********************************************************************
stk_blks - return count of indicated type of segments
**********************************************************************/
/*
unsigned int
stk_blks(stk)
STACK *stk;
{
return stk->current.count;
}
*/
/*********************************************************************
stk_unused - figure number of unused blocks available
**********************************************************************/
unsigned int
stk_unused()
{
return stk_blks(u_stack);
}
/*********************************************************************
stk_end - next pointer to be allocated in stack
**********************************************************************/
char *
stk_end(stk)
STACK *stk;
{
return (char *)nxtelem(stk, 0) + seg_size - stk->current.size;
}
/*********************************************************************
stk_space - add space onto indicated stack
**********************************************************************/
void *
stk_space(stk, size)
STACK *stk;
size_t size;
{
char *cptr;
/* save previous state */
stk->previous = stk->current;
/* if its not going to fit within current segment */
if(size > stk_avl(stk)){
/* if there are no segments in unused list */
if(nxtelem((ADDRESS)u_stack, 0) == (ADDRESS)NULL)
return (ADDRESS)NULL;
/* get a segment from unused list */
enlink((ADDRESS)stk, delink((ADDRESS)u_stack, 0), 0);
/*
{
ADDRESS ptr;
ptr = delink((ADDRESS)u_stack, 0);
enlink((ADDRESS)stk, ptr, 0);
}
*/
stk->current.size = seg_size;
--u_stack->current.count;
++stk->current.count;
}
cptr = ((char *)nxtelem((ADDRESS)stk, 0) + seg_size - stk->current.size);
stk->current.size -= size;
return (void *)cptr;
}
/*********************************************************************
stk_drop - shorten stack by last allocated amount.
**********************************************************************/
void
stk_drop(stk)
STACK *stk;
{
stk->current.size = stk->previous.size;
if(stk->current.size == seg_size){
enlink((ADDRESS)u_stack, delink((ADDRESS)stk, 0), 0);
++(u_stack->current.count);
--stk->current.count;
stk->previous.size =
stk->current.size = 0;
}
return;
}
/*********************************************************************
stk_push - create a stack frame by pushing previous frame onto stack
and saveing current frame.
**********************************************************************/
int
stk_push(stk)
STACK *stk;
{
STK_BLK *bptr;
bptr = (STK_BLK *)stk_space(stk, sizeof(STK_BLK));
if(bptr == (STK_BLK *)NULL)
return FALSE;
*bptr = stk->pushed;
stk->pushed = stk->current;
++stk->frame_count;
return TRUE;
}
/*********************************************************************
stk_pop - restore stack to frame previous to last stk_push
**********************************************************************/
int
stk_pop(stk)
STACK *stk;
{
/* check for stack under flow */
if(stk->frame_count == 0)
return FALSE;
--stk->frame_count;
/* move blocks onto unused list */
while(stk->pushed.count != stk->current.count){
--stk->current.count;
++u_stack->current.count;
enlink((ADDRESS)u_stack, delink((ADDRESS)stk, 0), 0);
}
/* adjust size of current block */
stk->current.size = stk->pushed.size;
/* restore previous frame */
stk->pushed = *((STK_BLK *)stk_end(stk) - 1);
/* remove frame from stack */
stk->previous = stk->current;
stk->previous.size += sizeof(STK_BLK);
stk_drop(stk);
return TRUE;
}